The present invention relates in general to the processing of packet data traffic in a communications system, and in particular to scheduling of data packets and admission control.
From the prior-art, there are two concepts known for the provision of quality of service in a packet oriented communications network.
One concept is the so-called Integrated Service Concept that is based on the reservation of resources for dedicated data packet streams. For the reservation of resources peer-to-peer signalling of requirements is needed before a transmission of payload data. All network nodes along a transmission path are requested to reserve corresponding resources. The Integrated Service Concept is described in: D. Clark et al., Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanisms, Proceedings SIGCOMM 92, August 1992.
A known signalling protocol is the so-called Resource Reservation Protocol RSVP, that is described in: L. Zhang et al., RSVP: A New Resource Reservation Protocol, IEEE Network Magazine, September 1993. RSVP is a receiver-oriented simplex protocol that reserves resources in one direction along a communications path. The receiver of the data flow is responsible for the initiation of the resource reservation.
The so-called TENET scheme is similar to the Integrated Service Concept (see D. Ferrari et al., A Scheme for Real-Time Channel Establishment in Wide Area Networks, IEEE Journal on Selected Areas of Communications, Vol. 8, pp. 368-379, 1990). It provides guaranteed delays for real-time services in a packet-switching wide-area network and allows bandwidth allocation per packet flow. In this scheme, clients declare their traffic characteristics and performance requirements at the time of communications channel establishment. After a channel is established, data packets are scheduled based on deadlines in the hosts and in the network nodes. In order to do so, a scheduler maintains at least three queues: one for deterministic packets, one for statistical packets, and the third for all other type of packets and all local tasks.
Another concept for the provision of quality of service is the so-called Differentiated Service Concept, which aims to simplify the classification and scheduling of packets with quality of service requirements by the use of priority bits in a protocol header. All packets belonging to a specific quality of service class will be marked with a corresponding priority bit combination in the Internet Protocol header. The packet flows are marked with the priority bits and policed according to a Service Level Agreement at the edge of the network. In the interior of the network, the packets are scheduled based on the priority bits. For the Differentiated Service Concept reference is given to S. Blake et al., An Architecture for Differentiated Services, IETF RFC 2475, December 1998.
Admission control of data packet streams and scheduling of the transmission order of data packets in order to minimise deadline violations of real-time or near real-time multimedia applications are important tasks in communication networks containing bottlenecks. In the following, the term xe2x80x98real-timexe2x80x99 should be understood also as xe2x80x98near real-timexe2x80x99 or, in general, as xe2x80x98time-criticalxe2x80x99. In heterogeneous networks, bottlenecks appear at network boundaries where traffic from one network is passed to another.
Certain real-time deadlines are usually not passed if only one data packet is delayed. Instead, usually a set of data packets spans up a synchronisation entity that has to arrive at the destination, e.g. to display a part of a multimedia output in time.
Application and intermediate nodes become more and more intelligent and allow for multimedia adaptation. This means that the amount of data bandwidth needed for the transmission of a certain multimedia object or presentation is not fixed. The adaptation process can be done by several means like dropping packets of lower priority, hierarchical multimedia coding, adaptive application, bandwidth adaptation gateways or even active networks that deploy processing elements within network nodes. Thus, in case of congestion, the bandwidth can vary in between a certain interval. The applications or the network itself may fulfil the needed adaptation task to vary the actual transmission rate in order to prevent deadline violations.
The existing admission control and scheduling schemes allow only for low bandwidth utilisation by means of peak rate allocations and delay guarantees that are given for bursty packet sources. Improved schemes are reaching a higher bandwidth utilisation by applying measurement algorithms that predict the actual available bandwidth by measuring the past bandwidth usage. However, measurement based algorithms provide only weak guarantees and only work efficient with a high amount of statistical multiplexing. Especially wireless networks are usually restricted in bandwidth capacity and thus, measurement based and deterministic admission control schemes have poor performances. One reason is that the existing schemes for packet scheduling are treating each packet in the same way. They are not able to detect past deadlines that are relevant for the receiving applications and thus, they cannot trigger processes that turn the current system into an error-free state.
Traditional schemes classify each packet stream into a priority class. In the Integrated Service Concept this priority class belongs to an average delay that packets of a particular stream will experience. In the Differentiated Service approach, this priority class belongs to a traffic type that should have less delay than other ones. The priority class is usually bounded to an average delay, the packet is expected to experience when admitted to that priority class. When considering multimedia streams with variable bit rates (like video streams), the packets of a single stream will not have the same delay requirements over the time. Instead, a scheduling by determination of a delivery deadline for each individual packet as proposed by the present invention provides a better performance than a priority based scheduling.
Therefore, it is an object of the present invention to provide an improved approach to packet oriented communications systems that overcomes these and other problems, in particular to allow a deadline-oriented scheduling of data packets carrying real-time data traffic.
The solution described in the invention is advantageous because of assignments of individual delivery deadlines to payload data packets that are subject to real-time processing. This is especially useful for data packets of a single multimedia stream with variable bit rates, due to different delay requirements that the packets have over the time. The calculation of a delivery deadline for each individual payload data packet allows an optimal scheduling of the payload data packet via a time-stamp based queue. Advantageously, synchronisation control parameters necessary for determination of deadlines are read from a synchronisation control packet SCP that is embedded in an incoming data packet stream. This guaranties an easy processing of control parameters and avoids additional signalling and complex protocol structures.
In a preferred use, apart from synchronisation control parameters, parameters like a packet error rate Pj and a bit rate Rj of a transmission channel for data packets are incorporated in the deadline calculation. In this way, the current system characteristics can be easily taken into account, which results in an improved performance.
It is further advantageous to perform an admission control before delivery deadlines are calculated for payload data packets at a packet scheduler. The decision to admit a real-time processing of a sub-stream of data packets depends on a minimum throughput requirement given by admission control parameters, which can be easily read from an admission control packet ACP. Advantageously, delivery deadline violations for data packets due to throughput lacks can be avoided, because data packets requiring a higher throughput than available are not admitted for real-time processing. Also, unnecessary calculations of delivery deadlines are avoided.
It is advantageous that the admission control takes into account a maximum throughput parameter Rh, This allows the choice of a more cost-effective throughput than the minimum required throughput R1 for a sub-stream, up to the maximum throughput Rh and in dependence of the available throughput.
It is advantageous to reject a sub-stream of data packets, which is not admitted for real-time processing, and to send It to the packet scheduler, because this allows still a best effort processing. A dropping of data packets and a corresponding loss of information can therefore be avoided.
Furthermore, an upper throughput limit Rh can avoid buffer overflows in the communications system or at the receiver of the data packet stream, because it is guarantied that data packets are not transmitted too fast.
It is advantageous to reject a sub-stream of data packets, which is not admitted for real-time processing, and to send it to the packet scheduler, because this allows still a best effort processing. A dropping of data packets and a corresponding loss of information can therefore be avoided.
Data packets that are rejected for real-time processing are sorted at the packet scheduler into a second queue FIFO In their order of appearance. This allows a best-effort processing according to a first inxe2x80x94first out strategy for data packets of the second queue FIFO.
Data packets from the first queue EDF are further processed according to their delivery deadlines, and data packets from the second queue FIFO are processed according to a first inxe2x80x94first out strategy. Advantageously, this puts the further processing of data packets under the established quality of service requirements into action.
An output interface OI prioritises data packets in the first EDF and the second queue FIFO. Advantageously, a blocking of data packets in one queue can be avoided by choice of a priority-strategy, which guaranties to a certain extend read-outs of data packets from both queues.
A throughput capability feedback is sent back along the data packet sub-stream""s transmission path via a modified admission control packet. Advantageously, this allows intermediate communications system nodes or a traffic source to adapt the traffic to the available throughput capabilities. In this way, rejections of data packets for real-time processing can be avoided to a high extend. The use of a modified admission control packet can avoid signalling overhead and a complex protocol structure.
Synchronisation control parameters are received from a header of an underlying network protocol. This allows payload encryption and authentication, and it supports the use of the so-called Internet protocols IPv4, IPv6 and IPSec, because synchronisation control parameters are not prevented from being read.
Deadline violations can be detected. Advantageously, this allows a triggering of countermeasures in order to guarantee the real-time processing of the data packets.
A payload data packet adaptation takes place. This allows the keeping of delivery deadlines for data packets. It supports furthermore an efficient use of the packet scheduler and other system resources, and it can avoid rejection or dropping of data packets.
Admission control parameters are received from a header of an underlying network protocol. This allows payload encryption and authentication, and it supports the use of the so-called Internet protocols IPv4, IPv6 and IPSec, because admission control parameters are not prevented from being read.
A network node that processes real-time data traffic comprises in addition a determining unit to determine a currently available throughput V, and a decision means for a decision about a real-time processing of an incoming data traffic flow. By means of the determining unit and the decision means it is possible to perform an admission control before deadlines are calculated for payload data packets at a packet scheduler. Advantageously, delivery deadline violations for data packets due to throughput lacks can be avoided, because data packets requiring a higher throughput than available are not admitted for real-time processing. Also, unnecessary calculations of delivery deadlines are avoided.
The network node comprises further a transfer unit to forward data packets that are admitted for real-time processing to the first queue EDF, and to forward data packets that are rejected for real-time processing to a second queue FIFO. This guaranties that all types of traffic can be processed. Data packets rejected for real-time processing can still be processed with best-effort quality.
In addition, an output interface OI prioritises data packets in the first EDF and the second queue FIFO. Advantageously, a blocking of data packets in one queue can be avoided by choice of a priority-strategy, which guaranties to a certain extend read-outs of data packets from both queues.
The network node comprises further a deadline violation handler and an adaptation unit. Therefore, countermeasures against delivery deadline violations can easily be triggered in order to guarantee the real-time processing of the data packets. A preferred countermeasure is the payload data packet adaptation, which allows the keeping of delivery deadlines. It supports furthermore an efficient use of the system resources, and it can avoid a rejection or a dropping of data packets.
The network node comprises further a radio base station. In a cellular communications network, and in particular in a radio access network, the available frequencies are limited resources. This results in limited bandwidths of communications channels. Advantageously, the present invention supports efficiently the provision of quality of service to clients requesting real-time multimedia services. In particular, the radio base station can accept only those clients, whose communication requests can be fulfilled.
It is advantageous that an admission control can easily be performed based on one or more admission control parameters R1 read from an admission control packet ACP, which is embedded in a data packet stream. A decision to admit a real-time processing of a sub-stream of data packets depends on a minimum throughput requirement given by said admission control parameters. Advantegeously, congestion due to throughput lacks at network nodes or applications can be avoided, because data packets requiring a higher throughput than available are not admitted for real-time processing. In addition, the admission control can take into account a maximum throughput parameter Rh. Therefore, the admission controller can choose a more cost-effective throughput than the minimum required throughput R1 for a sub-stream of data packets, up to the maximum throughput Rh and in dependence of the available throughput.
A network operator can charge different fees for different throughput rates provided to the customer. In order to increase the operator""s profit, said choice of a throughput rate for a sub-stream can be based on a gain-function provided by an operator, said gain function indicating e.g. cost per throughput-rate for the communications system, a network node or a transmission channel.
Furthermore, an upper throughput limit Rh can avoid buffer overflows in the communications system or at the receiver of the data packet stream, because it guaranties that data packets are not transmitted too fast.
Furthermore, it is advantageous to perform an admission control before deadlines are calculated for payload data packets. There is no need to calculate deadlines, if throughput requirements for a real-time processing of a sub-stream of data packets that are given by admission control parameters indicate under consideration of available throughput capabilities, that these deadlines cannot be kept. Advantageously, delivery deadline violations for data packets due to throughput lacks can be avoided, because data packets requiring another throughput than available are not admitted for real-time processing.
A throughput capability feedback is sent back along the data packet sub-stream""s transmission path via a modified admission control packet. Advantageously, this allows intermediate communications system nodes or a traffic source to adapt the traffic to the available throughput capabilities. In this way, rejections of data packets for real-time processing can be avoided to a high extent. The use of a modified admission control packet can also avoid signalling overhead and a complex protocol structure.
Data packets that are rejected for real-time processing are sorted into a second queue FIFO in their order of appearance. This allows an easy best-effort processing according to a first in - first out strategy for these data packets.
Data packets are prioritised for reading-out from the first queue EDF and the second queue FIFO. Advantageously, a blocking of data packets in one queue can be avoided by choice of a priority-strategy, which guaranties to a certain extend read-outs of data packets from both queues.
Deadline violations can be detected. Advantageously, this allows a triggering of countermeasures in order to guarantee the real-time processing of the data packets.
An adaptation of payload data packets is performed. This allows the keeping of delivery deadlines for data packets, in particular in the case of congestion or traffic load peaks. It supports furthermore an efficient use of system resources, and it can avoid rejection or dropping of data packets.
Admission control parameters and synchronisation control parameters are received from a header of an underlying network protocol. This allows payload encryption and authentication, and it supports the use of the so-called Internet protocols IPv4, IPv6 and IPSec, because admission control parameters are not prevented from being read.